The present invention relates to communication network protocols for medium access. In particular, the present invention relates to communication network protocols in the context of a wireless medium and in the context of communication networks that utilize fixed minimum packet sizes.
Data communications devices (DCDs) on certain common types of network must share the communication medium. The function of a medium access control (MAC) protocol is to allow each DCD the opportunity to seize the medium to transmit its data according to the rules of the protocol. In order to facilitate effective data communications, the opportunities to transmit should occur such that the wait time between opportunities is not excessive. In addition, access to the medium should be distributed fairly among the DCDs. A number of MAC protocols have been developed and fielded in wired networks.
These protocols include ALOHA, slotted-ALOHA, CSMA, and CSMA-CD. The ALOHA system is described in N. Abramson, "The ALOHA System--Another Alternative for Computer Communications," 1970 Fall Joint Computer Conference, AFIPS Conference Proceedings, Vol. 37, AFIPS Press, Montvale N.J., 1970, the contents of which are herein incorporated by reference. CSMA and CSMA-CD systems are described in Anthony S. Acampora, "An Introduction to Broadband Networks," Plenum Press, New York, N.Y., 1994, the contents of which are herein incorporated by reference.
ALOHA and slotted-ALOHA are random access schemes that could be adapted fairly easily to wireless networks. However, these MAC protocols suffer from poor maximum bus utilization.
While CSMA and CSMA-CD exhibit much better bus utilization, these protocols are much better suited to wired networks than wireless for the following reason: The operation of both CSMA and CSMA-CD depend upon each DCD in the network being able to sense when any of the other DCDs is transmitting. A DCD only transmits when it has determined that the bus is not currently in use by another DCD. This requirement becomes problematic in a wireless network since it often occurs that not every DCD in the network is within range of all the others.
FIG. 1 depicts a simple wireless network 100 with 3 DCDs 102. B communicates with both A and C. A and C are separated by too large a distance to detect when the other is transmitting, and are therefore obviously unable to communicate directly. To illustrate the problem that can arise, suppose A is transmitting to B. Since C cannot detect A's transmissions, it will mistakenly assume that the medium is not being used. Then, suppose that C, mistakenly believing that the bus is idle, attempts to transmit a message to B. As a result, a data collision occurs at B and the messages transmitted by both A and C are corrupted or one of the messages is lost. A situation such as this is commonly referred to as the "hidden terminal problem."
FIG. 2 depicts a solution to the hidden terminal problem. A wireless network 200 includes several DCDs 202 and a specialized central DCD 204, also referred to as an access point (AP) 204. Each DCD 202 communicates through AP 204. AP 204 allocates the use of the medium by all DCDs 202 making up the network. In order to be integrated into the network configuration, any remote DCD 202 must be within the coverage area of AP 204. This ensures that DCD 202 is able to receive, and will therefore adhere to, the commands issued by AP 204 concerning use of the medium.
MAC protocols using this network architecture have been implemented for cellular communication systems, wherein the base stations serve as APs and the cellular phones serve as the DCDs. However, because the nature of voice traffic is quasi-continuous and relatively low bandwidth, cellular MAC protocols are designed with circuit-switched channel assignments. The available spectrum is divided into frequency channels and/or time slots and/or spread spectrum spreading code channels that are assigned to a user for the duration of a call, regardless of whether there is any voice activity. This type of MAC protocol is inefficient in a typical computer or multi-media network due to the inherently bursty nature of its traffic. Exchanging bursty traffic over a circuit-switched network results in the circuit-switched connections frequently sitting idle.
With a demand-assigned protocol, usage of the bus is allocated dynamically by a bus arbiter according to the traffic demands of each DCD on the network. One example of a demand assigned MAC protocol is DQRUMA which is described in Mark J. Karol, Zhao Liu, and Kai Y. Eng, "An Efficient Demand-Assignment Multiple Access Protocol for Wireless Packet Networks". ACM/Baltzer Wireless Networks, Vol. 1, No. 3, pp. 267-279, 1995, the contents of which are herein incorporated by reference. Under this protocol, each DCD that has data to transmit notifies the AP. Any DCDs needing to use the bus submit their requests during a predefined, regularly reoccurring, time period called the request access (RA) slot. Whenever more than one DCD submits a request during the predefined period, all those requests are lost in a collision. In effect, the access request process operates like a slotted-ALOHA system, i.e. time-aligned random-access transmissions.
Upon receiving a valid access request, the AP sends back an acknowledgement message, and places the terminal's ID in a queue with other DCDs whose access requests were received but that have not yet been able to complete their transmissions. The AP manages the queue according to any one of many possible assignment algorithms. The AP notifies a given DCD shortly before its turn to use the bus. The DCD then uses the bus for a fixed, and reasonably short, period of time. If the DCD hasn't finished transmitting all of its data at the end of its allotted bus access period, it tacks a "piggyback request" onto the end of its transmission. The piggyback request lets the AP know that the DCD that just finished transmitting needs the bus again. This is equivalent to submitting a contention-free access request, helping to complete transfers which have already started. In addition, the piggyback request scheme significantly reduces the number of DCDs contending for access in the RA slot.
A demand-assigned protocol such as DQRUMA possesses many desirable features for a wireless data network as has just been described. However, it also possesses several undesirable qualities making it difficult to implement on many wireless networks. For instance, DQRUMA assumes the existence of simultaneous parallel uplink (traffic going into the AP) and downlink (traffic coming out of the AP) channels between the AP and the DCDs. If the parallel channels each have equal capacity, the bus can only operate at maximum efficiency when traffic into and out of the AP is perfectly balanced between uplink and downlink. Whenever the traffic is not balanced, one of the channels must operate below capacity. It is difficult, if not impossible, to reallocate bandwidth between the uplink and downlink channels in response to varying loads.
The only practical way to obtain two simultaneous channels in a wireless system is through frequency division duplexing (FDD), i.e., uplink traffic resides on one carrier frequency and downlink traffic resides on another. Often, frequency spectrum allocations for a given application do not lend themselves to the implementation of FDD systems. Unless the uplink and downlink frequency bands can be separated (into non-contiguous blocks) the analog filtering (diplexer) requirements for the wireless transceiver become extremely difficult if one is to avoid wasting a large portion of the spectrum.
In DQRUMA, requests for access to the bus, and the acknowledgements of those requests, are relatively short messages. The DQRUMA protocol is designed to use short requests and acknowledgement messages and longer data packets. However, in certain systems, such as networks that employ OFDM (Orthogonal Frequency Division Multiplexing), it is difficult to vary the size of the message bursts. Unless the data bursts in the system are very small, using the same size bursts to transmit access requests and acknowledgements will result in a many unused data bit in those bursts, adversely impacting spectral efficiency.
Furthermore, once a DCD has received an acknowledgement of its access request, it must continually listen to messages from the AP as it waits its turn to use the bus. This is a significant disadvantage for portable wireless DCDs, where battery life is a major consideration.
A medium access protocol for wired networks has been proposed in which multiple DCDs transmit overlapping messages during a single OFDM burst in such a way that the AP correctly receives each of the individual messages. See K. S. Jacobsen, J. A. C. Bingham, and J. M. Cioffi, "A Discrete Multitone-based Network Protocol for Multipoint-to-point Digital Communications in the CATV Reverse Channel," in 1995 Canadian Cable Television Association (CCTA) Technical Papers, May 1995, the contents of which are herein the contents of which are herein incorporated by reference. However, for this method to work properly, the AP must have knowledge of the channel between itself and each DCD transmitting the message. To obtain this channel knowledge, a separate channel training routine is executed, with the AP storing the channel measurements for later use. This is a workable solution for the time invariant (or very slowly varying) cable television channels contemplated by Jacobsen, et al.
However, in a wireless network the channel changes so rapidly that each message transmitted by a DCD propagates through an essentially unknown channel before reaching the AP. The Jacobsen, et al. method is thus unusable in the wireless context.
What is needed is a MAC protocol that efficiently accommodates fixed minimum packet sizes in a wireless contexts and that furthermore allows the DCD to deactivate its idle circuitry during bursts in which it neither transmits nor receives.